package com.lihepeng.leecode.recursive;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 排列问题的输入如果存在重复，比子集/组合问题稍微复杂一点
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 */
public class Solution47 {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> item = new LinkedList<>();
    boolean[]isUsed;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[]isUsed = new boolean[nums.length];
        dfs(nums);
        return result;
    }
    private void  dfs(int[]arrs){
        if (item.size() == arrs.length) {
            // 跳出
            result.add(new ArrayList<>(item));
            return;
        }
        for (int i=0;i<arrs.length ;i++) {
            // 剪枝
            if (i>0 && arrs[i]==arrs[i-1] && !isUsed[i-1] ){
                continue;
            }
            item.add(arrs[i]);
            isUsed[i] = true;
            dfs(arrs);
            item.removeLast();
            isUsed[i]=false;
        }
    }
}
